import java.util.Arrays;

public class BubbleSort {
    // 优化
    /*
    * 时间复杂度：O(N^2)
    * 最好情况【数组有序】可以达到 O(N)
    * 空间复杂度：O(1)
    * */
    public static void bubbleSort2(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = true;
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = false;
                }
            }
            // flag == true
            if(flag){
                break;
            }
        }
    }
    // 未优化
    /*
     * 时间复杂度：O(N^2) 【无论是最好情况，还是最坏情况，时间复杂度都不变】
     * 空间复杂度：O(1)
     * */
    public static void bubbleSort1(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        bubbleSort2(array);// 优化
        long end = System.currentTimeMillis();
        System.out.println(end - start);// 输出排序所需时间
        start = System.currentTimeMillis();
        bubbleSort1(array);// 未优化
        end = System.currentTimeMillis();
        System.out.println(end - start);//输出排序所需时间
    }
}
